from collections import Counter
from functools import lru_cache
from typing import List

MOD = 10 ** 9 + 7

# 质数列表
PRIME = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

# 质数数量
PRIME_NUM = len(PRIME)

# 需要过滤的数值：1 + 本身就是相同质数乘积列表
FILTER = {1, 4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28}

# 每个数的因子列表
FACTOR = {2: [2], 3: [3], 5: [5], 6: [2, 3], 7: [7], 10: [2, 5], 11: [11], 13: [13], 14: [2, 7], 15: [3, 5], 17: [17],
          19: [19], 21: [3, 7], 22: [2, 11], 23: [23], 26: [2, 13], 29: [29], 30: [2, 3, 5]}

# 每个数的状态列表
STATS = {2: 1, 3: 2, 5: 4, 6: 3, 7: 8, 10: 5, 11: 16, 13: 32, 14: 9, 15: 6, 17: 64, 19: 128, 21: 10, 22: 17, 23: 256,
         26: 33, 29: 512, 30: 7}


class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        # 统计每个数的数量
        count = Counter(nums)

        # 去除重复值
        nums = set(nums)

        # 过滤所有本身就是相同质数乘积的值
        nums = [num for num in nums if num not in FILTER]

        # 此时最多剩余18个数

        # 处理此时已没有数的情况
        if len(nums) == 0:
            return 0

        size = len(nums)

        # 深度优先搜索计算好子集数量
        # i <= 18
        # stat0 <= 1024

        @lru_cache(None)
        def dfs(i, stat0):
            # 边界条件
            if i == size:
                return 1 if stat0 != 0 else 0  # 如果当前有选择任意一个数，则返回1

            num = nums[i]  # 当前数值
            stat1 = STATS[num]

            # 其他情况
            if stat1 & stat0:  # 当前数不能被选择
                return dfs(i + 1, stat0)

            else:  # 当前数可以被选择
                v1 = dfs(i + 1, stat0 | stat1) * count[num]  # 选择当前数
                v2 = dfs(i + 1, stat0)  # 不选择当前数
                return (v1 + v2) % MOD

        return (dfs(0, 0) * pow(2, count[1], mod=MOD)) % MOD  # 考虑选择1的数量


if __name__ == "__main__":
    print(Solution().numberOfGoodSubsets(nums=[1, 2, 3, 4]))  # 6
    print(Solution().numberOfGoodSubsets(nums=[4, 2, 3, 15]))  # 5
    print(Solution().numberOfGoodSubsets(nums=[6, 8, 1, 8, 6, 5, 6, 11, 17]))  # 62
